Grokking Google Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Google Easy
Add Binary (easy)
Solution: Add Binary
Valid Mountain Array (easy)
Solution: Valid Mountain Array
Set Mismatch (easy)
Solution: Set Mismatch
Is Subsequence (easy)
Solution: Is Subsequence
Length of Last Word (easy)
Solution: Length of Last Word
Search Insert Position (easy)
Solution: Search Insert Position
Repeated Substring Pattern (easy)
Solution: Repeated Substring Pattern
Monotonic Array (easy)
Solution: Monotonic Array
Count Nodes Equal to Average of Subtree (easy)
Solution: Count Nodes Equal to Average of Subtree
Find the Difference (easy)
Solution: Find the Difference
How Many Numbers Are Smaller Than the Current Number (easy)
Solution: How Many Numbers Are Smaller Than the Current Number
Binary Tree Paths (easy)
Solution: Binary Tree Paths
Find the Difference of Two Arrays (easy)
Solution: Find the Difference of Two Arrays
Merge Strings Alternately (easy)
Solution: Merge Strings Alternately
Reverse a LinkedList (easy)
Solution: Reverse a LinkedList
Google Medium
Gray Code (medium)
Solution: Gray Code
2 Keys Keyboard (medium)
Solution: 2 Keys Keyboard
Arithmetic Slices (medium)
Solution: Arithmetic Slices
Unique Length-3 Palindromic Subsequences (medium)
Solution: Unique Length-3 Palindromic Subsequences
Minimum Difference Between Largest and Smallest Value in Three Moves (medium)
Solution: Minimum Difference Between Largest and Smallest Value in Three Moves
Letter Combinations of a Phone Number (medium)
Solution: Letter Combinations of a Phone Number
01 Matrix (medium)
Solution: 01 Matrix
Maximum Points You Can Obtain from Cards (medium)
Solution: Maximum Points You Can Obtain from Cards
Strobogrammatic Number II (medium)
Solution: Strobogrammatic Number II
Maximum Length of Semi-Decreasing Subarrays (medium)
Solution: Maximum Length of Semi-Decreasing Subarrays
Minimum Area Rectangle (medium)
Solution: Minimum Area Rectangle
Count Unreachable Pairs of Nodes in an Undirected Graph (medium)
Solution: Count Unreachable Pairs of Nodes in an Undirected Graph
Single Number II (medium)
Solution: Single Number II
4Sum II (medium)
Solution: 4Sum II
Furthest Building You Can Reach (medium)
Solution: Furthest Building You Can Reach
Minimizing Array After Replacing Pairs With Their Product (medium)
Solution: Minimizing Array After Replacing Pairs With Their Product
Fair Distribution of Cookies (medium)
Solution: Fair Distribution of Cookies
Find Leaves of Binary Tree (medium)
Solution: Find Leaves of Binary Tree
Rotate Image (medium)
Solution: Rotate Image
Combination Sum (medium)
Solution: Combination Sum
Implement Trie (Prefix Tree) (medium)
Solution: Implement Trie (Prefix Tree)
Number of Islands (medium)
Solution: Number of Islands
Edit Distance (medium)
Solution: Edit Distance
Container With Most Water (Medium)
Solution: Container With Most Water
Meeting Rooms II (medium)
Solution: Meeting Rooms II
Shortest Subarray with Sum at Least K (hard)
Solution: Shortest Subarray with Sum at Least K
Reverse Pairs (hard)
Solution: Reverse Pairs
Nth Magical Number (hard)
Solution: Nth Magical Number
Candy (hard)
Solution: Candy
Arithmetic Slices II - Subsequence (hard)
Solution: Arithmetic Slices II - Subsequence
Burst Balloons (hard)
Solution: Burst Balloons
Sum of Distances in Tree (hard)
Solution: Sum of Distances in Tree
Maximum Score of a Good Subarray (hard)
Solution: Maximum Score of a Good Subarray
Trapping Rain Water (hard)
Solution: Trapping Rain Water
First Missing Positive (hard)
Solution: First Missing Positive
Solution: 01 Matrix

Problem Statement

Given an m x n matrix mat containing only 0 and 1, return the distance of the nearest 0 for each cell.

The distance between two adjacent cells of mat is 1.

Examples

Example 1:

  • Input: mat =
[[1,0,1,1],
 [1,1,1,1],
 [1,1,1,0]]
  • Expected Output:
[[1,0,1,2],
 [2,1,2,1],
 [3,2,1,0]]
  • Justification: Each cell updates to the minimum distance to a zero, with the edges being closest and moving inward, the distance increases.

Example 2:

  • Input: mat =
[[0,1,1],
 [1,1,0],
 [1,0,1]]
  • Expected Output:
[[0,1,1],
 [1,1,0],
 [1,0,1]]
  • Justification: Starting with the zeros, we update their neighbors. The zeros remain zeros since they are already at the nearest zero. The ones directly adjacent to a zero become ones, demonstrating their proximity.

Example 3:

  • Input: mat =
[[1,1,0],
 [0,1,1],
 [1,1,1]]
  • Expected Output:
[[1,1,0],
 [0,1,1],
 [1,2,2]]
  • Justification: Output matrix represents the shortest path to a zero for each cell.

Constraints:

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n <= 104
  • 1 <= m * n <= 104
  • mat[i][j] is either 0 or 1.
  • There is at least one 0 in mat.

Solution

To solve this problem, we start by identifying all the cells containing 0s and marking them as starting points. From these points, we perform a breadth-first search (BFS) to explore all their neighboring cells. This approach ensures that each cell is updated with the shortest distance to the nearest zero, considering only vertical and horizontal movements. Using BFS is effective because it naturally explores all possible paths from each zero, updating distances in a way that guarantees the shortest path is found first before moving on to explore longer paths. This strategy is efficient and ensures that every cell is assigned the correct minimum distance.

The choice of BFS for this solution is crucial because it allows us to layer the exploration of the matrix, ensuring that each cell's distance is updated relative to its proximity to the nearest zero. As we iterate through the matrix, we maintain a queue to manage the cells being explored, updating their distance based on their position relative to the nearest zero. This method is not only systematic but also ensures that all possible paths are considered, providing an optimal solution to the problem.

Step-by-Step Algorithm

  1. Initialization:

    • Determine the dimensions of the input matrix, m (number of rows) and n (number of columns).
    • Create a queue to store the positions (row and column indices) of all the 0s in the matrix.
    • Iterate over the matrix. For each element:
      • If it's a 0, add its position to the queue.
      • If it's a 1, change its value to Integer.MAX_VALUE (in Java) or an equivalent large number to indicate it's not yet visited or updated.
  2. Define Directions:

    • Create an array or list of directions to move from any cell (up, down, left, right).
  3. Process Queue:

    • While the queue is not empty, perform the following:
      • Remove an element (position) from the queue.
      • Iterate over the defined directions, and for each direction, calculate the new position.
      • If the new position is within bounds and its value is greater than the current position's value plus 1 (indicating a shorter path to a 0 has been found):
        • Update the new position's value to be the current position's value plus 1.
        • Add the new position to the queue to later check its neighbors.
  4. Return Updated Matrix:

    • After the queue is empty (all positions processed), return the modified matrix as the final result.

Algorithm Walkthrough

Let's consider the Input: mat = [[1,0,1,1], [1,1,1,1], [1,1,1,0]]

Initial Matrix

1 0 1 1
1 1 1 1
1 1 1 0
Image

Step 1: Initialization

  • Queue = {(0, 1), (2, 3)} (Coordinates of the 0s)
  • Update all 1s to infinity (Integer.MAX_VALUE or a symbolic equivalent for clarity)

Matrix becomes:

∞ 0 ∞ ∞
∞ ∞ ∞ ∞
∞ ∞ ∞ 0

Step 2: Processing (Queue: {(0, 1), (2, 3)})

  • First iteration (0, 1):
    • Top: Out of bounds
    • Bottom: (1, 1) updated to 1 (from ∞)
    • Left: (0, 0) updated to 1 (from ∞)
    • Right: (0, 2) updated to 1 (from ∞)
  • Queue becomes: {(2, 3), (1, 1), (0, 0), (0, 2)}

After first iteration matrix:

1 0 1 ∞
∞ 1 ∞ ∞
∞ ∞ ∞ 0
  • Second iteration (2, 3):
    • Top: (1, 3) updated to 1 (from ∞)
    • Bottom: Out of bounds
    • Left: (2, 2) updated to 1 (from ∞)
    • Right: Out of bounds
  • Queue becomes: {(1, 1), (0, 0), (0, 2), (1, 3), (2, 2)}

Matrix after second iteration:

1 0 1 ∞
∞ 1 ∞ 1
∞ ∞ 1 0
  • Third Iteration (1, 1):

    • Top: (0, 1) already 0, no update.
    • Bottom: (2, 1) updated to 2 (from ∞).
    • Left: (1, 0) updated to 2 (from ∞).
    • Right: (1, 2) updated to 2 (from ∞).
  • Updated Queue: {(0, 0), (0, 2), (1, 3), (2, 2), (2, 1), (1, 0), (1, 2)}

Matrix after this step:

1 0 1 ∞
2 1 2 1
∞ 2 1 0
  • Fourth Iteration (0, 0):

    • Top: Out of bounds.
    • Bottom: (1, 0) already 2, no update.
    • Left: Out of bounds.
    • Right: (0, 1) already 0, no update.
  • No updates made, proceed to the next cell in the queue.

  • Fifth Iteration (0, 2):

    • Top: Out of bounds.
    • Bottom: (1, 2) already 2, no update.
    • Left: (0, 1) already 0, no update.
    • Right: (0, 3) updated to 2 (from ∞).
  • Updated Queue: {(1, 3), (2, 2), (2, 1), (1, 0), (1, 2), (0, 3)}

Matrix after this step:

1 0 1 2
2 1 2 1
∞ 2 1 0
  • Sixth Iteration (1, 3):

    • Mat remains the same.
  • Seventh Iteration (2, 2):

    • Mat remains the same.
  • Eighth Iteration (2, 1):

    • Top: (1, 1) already 1, no update
    • Bottom: Out of bound
    • Left: (2, 0) updated to 3 (from ∞).
    • Right: (2, 3) already 0, no update
  • Updated Queue: {(1, 0), (1, 2), (0, 3), (2, 0)}

Matrix after this step:

1 0 1 2
2 1 2 1
3 2 1 0

Subsequent Iterations

Proceeding with the next elements in the queue, updating neighbors where applicable. Each step involves checking the top, bottom, left, and right neighbors for potential updates, following the same pattern as demonstrated.

Final Iteration Steps

  • Process (1, 0), (1, 2), (0, 3), (2, 0): Each of these cells will have its neighbors checked. Updates are made only if the current distance + 1 is less than the neighbor's distance.

  • After processing all elements in the queue, the final distances are calculated. Each '∞' symbol gets replaced with the calculated minimum distance to the nearest '0'.

Final Matrix

1 0 1 2
2 1 2 1
3 2 1 0

This matrix represents the completed calculation, with each cell now showing the minimum distance to the nearest 0, adhering strictly to the described approach and order of neighbor visitation.

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

Time Complexity

  • Best and Worst Case:
    • The algorithm goes through every cell in the matrix at least once. Each cell is inserted into the queue only once, and each removal from the queue is followed by a constant number of operations (checking and potentially updating its neighbors).
    • Since each cell's neighbors are processed at most once, the overall time complexity is linear in terms of the number of cells, , where (m) is the number of rows and (n) is the number of columns in the matrix.

Space Complexity

  • Worst Case:
    • In the worst case, the queue might contain all the cells of the matrix before starting to empty, especially if the matrix starts with all 1s and there's only one 0 at the edge or corner. Thus, the space complexity is also due to the queue storage.
01 Matrix (medium)
Maximum Points You Can Obtain from Cards (medium)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity